package com.mgface.alg.链表;

import static com.mgface.alg.链表.Test.Node;
/**
 * @author wanyuxiang
 * @version 1.0
 * @project Java_Alg
 * @create 2019-11-04 10:18
 * @desc 检查一个较大的单链表是否有环
 **/
public class Test2 {
    public static Node constructList(){
        Node head = new Node();
        head.next = null;
        Node current = head;

        for (int i = 1;i < 8; i++) {
            Node temp = new Node();
            temp.value = i;
            temp.next = null;
            current.next = temp;
            current = temp;
        }
        current.next = head.next.next.next;
        return head;
    }

    public static Node isLoop(Node head){
        if (head==null||head.next==null) {
            return null;
        }
        Node slow = head.next;
        Node fast = head.next;
        while (fast!=null&&fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow==fast){
                return slow;
            }
        }
        return null;
    }
    public static Node findLoopNode(Node head,Node meetNode){
        Node first = head.next;
        Node second = meetNode;
        while (first!=second){
            first = first.next;
            second= second.next;
        }
        return first;
    }
    public static void main(String[] args) {
        Node head= constructList();
        Node meetNode = isLoop(head);
        Node loopNode = null;
        if (meetNode!=null){
            System.out.println("有环......");
            loopNode = findLoopNode(head,meetNode);
            System.out.println("环的入口为:"+loopNode.value);
        }else {
            System.out.println("无环......");
        }
    }
}
